package first.niuke.huawei.mediumDifficulty;

import java.util.Stack;

/**
 * @ClassName HJ43
 * @description:
 * @author: 荣燊
 * @create: 2021-07-13 15:01
 **/
public class HJ43 {
    // 迷宫问题,yyds

    // 存储当前路径
    static Stack<Node> stack_tmp = new Stack<>();
    // 存储最佳路径
    static Stack<Node> stack_best = new Stack<>();

    public static void main(String[] args) {
        int[][] tmp = new int[][]{
                        {0, 1, 0, 0, 0},
                        {0, 1, 0, 1, 0},
                        {0, 0, 0, 0, 1},
                        {0, 1, 1, 1, 0},
                        {0, 0, 0, 0, 0}
                    };
        dfs(tmp, 0, 0);
        // 输出的栈，临时做转化
        Stack<Node> stack_prt = new Stack<>();
        while (!stack_best.isEmpty()) {
//            System.out.println("(" + stack_best.peek().x + "," + stack_best.peek().y +")");
            stack_prt.push(new Node(stack_best.peek().x, stack_best.peek().y));
            stack_best.pop();
        }
        while (!stack_prt.isEmpty()) {
            System.out.println("(" + stack_prt.peek().x + "," + stack_prt.peek().y +")");
            stack_prt.pop();
        }
    }

    static void dfs(int[][] a, int i, int j) {
        a[i][j] = 1; //表示该节点已走
        stack_tmp.push(new Node(i, j)); //该节点加入路径中

        // 判断是否已经走到最终的节点，以及是否是最优路径
        if (i == a.length-1 && j == a[0].length-1) {
            if (stack_best.isEmpty() || stack_best.size() > stack_tmp.size()) {
                stack_best = (Stack<Node>) stack_tmp.clone();
            }
        }

        if (i-1 >= 0 && a[i-1][j] == 0) {
            dfs(a, i-1, j);
        }
        if (j-1 >= 0 && a[i][j-1] == 0) {
            dfs(a, i, j-1);
        }
        if (i+1 < a.length && a[i+1][j] == 0) {
            dfs(a, i+1, j);
        }
        if (j+1 < a[0].length && a[i][j+1] == 0) {
            dfs(a, i, j+1);
        }

        // 如果上面的上下左右都走不通了，那么就要恢复现场了。
        a[i][j] = 0;
        stack_tmp.pop();
    }

    static class Node {
        int x;
        int y;
        Node (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

}
